﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <string>
#include <iostream>
using namespace std;

// 和大于等于 target 的最短子数组
// 前缀和 + 二分查找
/*
int minSubArrayLen(int target, vector<int>& nums)
{
    // 求前缀和
    int n=static_cast<int>(nums.size());
    std::vector<int> v(nums.size()+1,0);
    for(int i=1;i<=n;++i)
    {
        v[i]=v[i-1]+nums[i-1];
    }

    // 二分
    int ans=INT_MAX;
    for(int i=1;i<=n;++i)
    {
        int tmp=target+v[i-1];

        auto index=lower_bound(v.begin(),v.end(),tmp);
        if(index!=v.end())
        {
            int x=static_cast<int>((index-v.begin())-i+1);
            ans=std::min(ans,x);
        }
    }

    return ans==INT_MAX?0:ans;
}
*/

// 滑动窗口
/*
int minSubArrayLen(int target, vector<int>& nums)
{
    int n=static_cast<int>(nums.size());
    int start=0;
    int end=0;
    int sum=0;

    int ans=INT_MAX;
    while(end<n)
    {
        sum+=nums[end];
        while(sum>=target) // 如果和大于target,则从start开始减
        {
            // 更新长度
            ans=std::min(ans,end-start+1);
            sum-=nums[start];
            ++start;
        }
        ++end;
    }

    return ans==INT_MAX?0:ans;
}
*/

// 乘积小于 K 的子数组
// 暴力解法---超时
/*
int numSubarrayProductLessThanK(vector<int>& nums, int k)
{
    int n=static_cast<int>(nums.size());

    int count=0;
    for(int i=0;i<n;++i)
    {
        int mul=1;
        for(int j=i;j<n;++j)
        {
            mul*=nums[j];
            if(mul<k)
            {
                count++;
            }
            else
            {
                break;
            }
        }
    }

    return count;
}
*/

// 滑动窗口
/*
int numSubarrayProductLessThanK(vector<int>& nums, int k)
{
    if(0==k||k==1)
        return 0;
    int n=static_cast<int>(nums.size());
    int l=0;
    int r=0;
    int count=0;
    int mul=1;

    while(r<n)
    {
        mul*=nums[r];
        while(mul>=k)
        {
            mul/=nums[l];
            ++l;
        }
        count=count+r-l+1;
        ++r;
    }

    return count;
}
*/

// 和为 k 的子数组
// 暴力
/*
int subarraySum(vector<int>& nums, int k)
{
    int n=static_cast<int>(nums.size());

    int count=0;

    for(int i=0;i<n;++i)
    {
        int sum=0;
        for(int j=i;j<n;++j)
        {
            sum+=nums[j];
            if(sum==k)
            {
                count++;
            }
        }
    }
    return count;
}
*/

// 哈希+前缀和
/*
class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int prefix_sum = 0, count = 0;
        for (int e : nums)
        {
            prefix_sum += e;
            if (hash.find(prefix_sum - k) != hash.end())
            {
                count += hash[prefix_sum - k];
            }
            // ++ 操作得写在 if 之后，因为在比较前不应该改变 hash 的状态
            // 自身的取值不纳入考虑，不作为解，尤其当 k = 0 时
            hash[prefix_sum]++;
        }
        return count;
    }
};
*/

// 回文子字符串的个数

// 暴力
/*
// 1.判断一个串是否为回文串
bool isPalindromeStr(const std::string& str)
{
    int l = 0;
    int r = static_cast<int>(str.size() - 1);

    while (l < r)
    {
        if (str[l++] != str[r--])
            return false;
    }

    return true;
}

int countSubstrings(string s)
{
    int n = static_cast<int>(s.size());
    // 2.生成s所有可能的子串
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            if (isPalindromeStr(s.substr(i, j - i + 1)))
            {
                ans++;
            }
        }
    }
    return ans;
}
*/

// 中心扩展
/*
int countSubstrings(string s)
{
    int n=static_cast<int>(s.size());
    int ans=0;

    for(int i=0;i<2*n-1;++i)
    {
        int l=i/2;
        int r=i/2+i%2;

        while(l>=0 && r<n && s[l]==s[r])
        {
            l--;
            r++;
            ans++;
        }
    }

    return ans;
}
*/

// 动态规划
/*
int countSubstrings(string s)
{
    int n=static_cast<int>(s.size());
    // 定义valid[i][j]为从第i个字符到第j个字符的子串是否为回文串的bool值
    std::vector<std::vector<bool>> valid(n,std::vector<bool>(n,false));

    int ans=0;
    // 一定要从下到上，从左到右遍历，这样可以保证dp[i+1][j−1]dp[i + 1][j - 1]dp[i+1][j−1]都是经过计算的
    for(int i = n - 1; i >= 0; i--) // 反向遍历,保证状态转移
    {
        for(int j=i;j<n;++j)
        {
            if(i==j)
            {
                valid[i][j]=true;
            }
            else if(i+1==j && s[i]==s[j]) // 避免越界及误判
            {
                valid[i][j]=true;
            }
            else if(s[i]==s[j]) // 如果s[i]==s[j],则需要根据i+1到j-1的串来判断
            {
                valid[i][j]=valid[i+1][j-1]; // 左下角的元素
            }

            if(valid[i][j])
            {
                ans++;
            }
        }
    }

    return ans;
}
*/